home *** CD-ROM | disk | FTP | other *** search
/ Mac Magazin/MacEasy 21 / Mac Magazin and MacEasy Magazine CD - Issue 21.iso / Wissenschaft & Technik / yorick12vr1-nofpu folder / include / msort.i < prev    next >
Text File  |  1995-07-26  |  3KB  |  79 lines
  1. /*
  2.    MSORT.I
  3.    Multiple key sort routine.
  4.  
  5.    $Id$
  6.  */
  7. /*    Copyright (c) 1994.  The Regents of the University of California.
  8.                     All rights reserved.  */
  9.  
  10. func msort(x, ..)
  11. /* DOCUMENT msort(x1, x2, x3, ...)
  12.      returns an index list which sorts the array X1 into increasing
  13.      order.  Where X1 values are equal, the list will sort X2 into
  14.      increasing order.  Where both X1 and X2 are equal, X3 will be
  15.      in increasing order, and so on.  Finally, where all of the keys
  16.      are equal, the returned list will leave the order unchanged
  17.      from the input keys.
  18.  
  19.      The Xi may be numbers or strings (e.g.- X1 could be an integer
  20.      while X2 was a string, and X3 was a real).  The Xi must all be
  21.      conformable, and each dimension of X1 must be as large as the
  22.      corresponding dimension of any otehr Xi.
  23.  
  24.      Hence, msort(x) will return the same list as sort(x), except
  25.      where the values of x are equal, in which case msort leaves
  26.      the order unchanged, while sort non-deterministically permutes
  27.      equal elements.  This feature may cost a factor of two in speed,
  28.      so don't use it unless you really need it.  In general, msort
  29.      will call sort up to twice per input argument.
  30.  
  31.    SEE ALSO: sort, msort_rank
  32.  */
  33. {
  34.   mxrank= numberof(x)-1;
  35.   local list;
  36.   rank= msort_rank(x, list);
  37.   if (max(rank)==mxrank) return list;
  38.  
  39.   norm= 1.0/(mxrank+1.0);
  40.   if (1.0+norm == 1.0) error, pr1(mxrank+1)+" is too large an array";
  41.  
  42.   n= more_args();
  43.   while (n--) {
  44.     x= next_arg();
  45.     rank+= msort_rank(x)*norm;     /* adjust rank for next key */
  46.     rank= msort_rank(rank, list);  /* renormalize adjusted rank */
  47.     if (max(rank)==mxrank) return list;
  48.   }
  49.  
  50.   /* use indgen as final key guaranteed to break up any remaining
  51.      equal values */
  52.   return sort(rank+indgen(0:mxrank)*norm);
  53. }
  54.  
  55. func msort_rank(x, &list)
  56. /* DOCUMENT msort_rank(x)
  57.             msort_rank(x, list)
  58.      returns a list of longs the same size and shape as X, whose
  59.      values are the "rank" of the corresponding element of X among
  60.      all the elements of X -- the smallest element has rank 0 and
  61.      the largest has the largest rank, which is equal to one less
  62.      than the number of distinct values in the array X.
  63.  
  64.      If LIST is present, it is set to the order list returned by
  65.      sort(x(*)).
  66.  
  67.    SEE ALSO: msort, sort
  68.  */
  69. {
  70.   rank= array(0, dimsof(x));
  71.   if (numberof(x)<2) return rank;
  72.   void= use_origins(0);
  73.   list= sort(x(*));
  74.   x= x(list);
  75.   x= (x(1:-1)!=x(2:0))(cum);  /* NOT dif -- x may be strings */
  76.   rank(list)= x;
  77.   return rank;
  78. }
  79.